⟸ Go Back ⟸

Exercise 12 (Homework 1).

(pigeonhole principle)

Arbitrary long walks in graphs

Given a directed graph G (with loops) with n vertices, and two vertices s, t in it, show that if there exists a walk in G from s to t of length > n then there are arbitrary long walks from s to t. In other words that there exists an n_0\in \mathbb N such that for every m\geq n_0 there is a walk in G from s to t of length \geq m.

Recall that a walk from s to t in a graph G is a sequence of vertices v_0,\dots,v_\ell such that v_0=s, v_\ell=t and for each i, (v_i,v_{i+1}) is an edge in G. It is not required for the vertices or edges to be distict. The length of the walk is \ell.